When developing integrated circuits that perform floating-point arithmetic, designers typically base the representations of floating-point (FP) numbers and the constraints on the results of arithmetic operations on published standards, such as the well-known “IEEE standard for binary floating point arithmetics, An American National Standard, ANSI/IEEE Std 754-1995”. Adherence to such standards guarantees that the circuitry will perform floating-point arithmetic with acceptable and predictable results. Although it is a relatively straightforward task to implement floating-point standards in a floating-point hardware unit, designers usually make modifications in the implementation to improve performance in special cases. Because of this, it is necessary to verify compliance of the finished design to the selected standard. In many instances, errors in floating-point implementation escape detection and find their way into production. Cases such as the well-known Pentium bug show that the verification process in this area is still far from being optimal. The ever-growing demand for increased performance, reduced time-to-market, and decreasing tolerance for errors all combine to make verification increasingly harder. The term “floating-point unit” herein denotes any device or system capable of performing binary floating-point computations by any means including, but not limited to, hardware, firmware, programmable logic arrays, and software.
There are many places problems can occur in the implementation of a floating-point unit, ranging from data problems on single instructions to the correct handling of sequences of instructions in which back-to-back events challenge superscalar implementations. This complexity stems both from the interpretation of the specification (architecture) as well as the peculiarities of the implementation (microarchitecture).
Although there is on-going work to develop formal proofs of adherence to a standard, formal methods are still far from providing a complete answer to the problem. The simulation of test cases (generating the test case data, running the test case on the target floating-point unit, and confirming the accuracy of the result), has traditionally been employed for verification, and therefore remains the foundation of the verification process.
It is the generating of floating-point test cases that is of interest regarding the present invention.
Test Case Generating Background
First, it is clear that there is an enormous, practically unlimited number of different calculation cases to test. In practice then, simulation can be done on only a very small portion of the existing space. Reducing the enormous number of potential test cases to a manageable number that can actually be tested is done through placing suitable constraints on the machine numbers so that the constrained set of machine numbers used in the test will be representative of a particular aspect of testing, but will still constitute a sufficient number of cases for thorough testing. (Constraints are discussed below.)
The rationale behind verification-by-simulation is that one acquires confidence in the correctness of a floating-point unit design by running a set of test cases that encompass a sufficiently large number of different cases, which in some sense is assumed to be a representative sample of the full space. The ability of the floating-point unit design to correctly handle all cases is inferred from the correct handling of the cases actually tested.
To confidently make the above inference requires the building of a set of test cases that covers all special implementations of the floating-point unit design. The problem then becomes one of how best to do this. Since both the architecture specification and the microarchitecture implementation tend to yield a myriad of special cases, generating the test cases using a uniform random distribution over the entire floating-point space would be highly inefficient. For example, it is common that executing an FADD instruction that results in a sum of zero exercises a specific part of the design logic, and therefore such a case should be verified. The probability of randomly generating two floating-point numbers that add to zero, however, is extremely low. Therefore, prior-art random test generators usually possess some internal Testing Knowledge (TK) to bias the test generation towards cases of interest. Such test generators are described in “Model-Based Test Generation For Processor Design Verification” by Y. Lichtenstein, Y. Malka and A. Aharon, Innovative Applications of Artificial Intelligence (IAAI), AAAI Press, 1994; “Constraint Satisfaction for Test Program Generation” by L. Fournier, D. Lewin, M. Levinger, E. Roytman and Gil Shurek, Int. Phoenix Conference on Computers and Communications, March 1995; and “Test Program Generation for Functional Verification of PowerPC Processors in IBM” by A. Aharon, D. Goodman, M. Levinger, Y. Lichtenstein, Y. Malka, C. Metzger, M. Molcho and G. Shurek, 32nd Design Automation Conference, San Francisco, June 1995, pp. 279–285.
In effect, TK changes the probability distribution of a test space, better adapting that test space to existing knowledge. In a test-generator described in the foregoing references, the TK is in the form of C-language functions (called “generation functions”) which can be added incrementally to the generator, such as by the users themselves. A serious limitation of this prior art approach, however, is that such generation functions are very complex and difficult to write, requiring a deep understanding of the Floating Point unit design. In practice, then, very few generating functions have been added.
Definitions
The following terms and abbreviations are used herein:
Biased exponentthe sum of the exponent and aconstant “bias” selected so that thebiased exponent is always non-negativeover the exponent's range. The use ofa biased exponent allows representingboth positive and negative exponentswithout requiring a sign.Denormal(a “denormalized number”) a non-zeroFP number whose exponent has areserved value (usually the minimumpermitted by the format), and whoseexplicit or implicit leading bit ofthe significand is zero.Exponentthe component of a binaryfloating-point number that normallyspecifies the integer power of 2 whichis multiplied by the significand toexpress the value of the representednumber. In certain formats, reservedvalues of the exponent are used toindicate that the number isdenormalized.FPFloating-Point. A binary loating-pointnumber contains a sign, an exponent,and a significand.FxPFixed-PointMaska template for a binary number. A maskis a series of characters, each ofwhich represents allowable values forthe bit in the corresponding positionof the binary number. There is exactlyone character in a mask for each bitof the corresponding binary number,with characters in a one-to-onecorrespondence with the bits.Allowable mask characters include ‘0’,‘1’, and ‘x’. A ‘0’ characterindicates that the corresponding bitof the binary number must be a 0,whereas a ‘1’ character indicates thatthe corresponding bit of the binarynumber must be a 1. An ‘x’ characteris a “don't care”, meaning that thecorresponding bit of the binary numbermay be either 0 or 1. In afloating-point number, it is possibleto specify separate masks for sign,exponent, and significand.NaN(“Not a Number”) a symbolic entityencoded in FP format.Normal(a “normalized number”) a non-zero FPnumber whose explicit or implicitleading bit of the significand is one.Signficandthe component of a binary FP numberthat consists of a single explicit orimplicit leading bit to the left of animplied binary point and a field offraction bits to the right of thebinary point. Even in implementationswhere the significand's leading bit(to the left of the binary point) isimplied and is not explicitly present,the significand still includes thatleading bit. Note that a significanddiffers from a “mantissa” in that amantissa includes only the fractionfield to the right of the binarypoint, whereas a significand alsoincludes the bit to the left of thebinary point. The concept of mantissamay be defined in such a way toinclude all of the bits of thesignificand, including the leftmostbit and not only the fraction bits. Inthis case and for a binary normalizedsignificand, the mantissa would simplybe the significand shifted one placeto the right, or divided by a scalingfactor of 2.The Set of Machine Numbers
For purposes of illustration, a non-limiting example of a binary floating-point number system is the IEEE standard 754 previously referenced. We assume that three integer constants are given, Emin, Emax, p. The machine numbers are those which can be represented in the form v=(−1)s×2E×b0b1b2 . . . bp−i, where sε{0, 1} represents the sign of v. E, representing the exponent of v, is an integer satisfying Emin≦E≦Emax. The bit values are denoted as biε{0, 1}, and p is the “precision” of the system. The significand is b0b1b2 . . . bp−1, whose binary point lies between b0 and b1. All machine numbers v that satisfy |v|≧2Emin are assumed to be normalized (b0=1). Those machine numbers which are smaller in magnitude than 2Emin (including zero) have E−Emin and are denormalized (b0=0). Thus, each machine number has a unique representation (note that the IEEE standard 754 requires the same uniqueness for single and double formats but not for extended formats).
Binary Representations of Machine Numbers and the Mask Constraint
Machine numbers are herein represented as strings of binary digits (bits). This is true for fixed point numbers as well as for floating point numbers. A mask related to a number is a string of characters of the same length (number of bits) as the number, all of whose characters are in the set {‘0’, ‘1’, ‘x’}. A number and a mask are compatible if all the following conditions are met:                The number and the mask are of the same length (hence each bit of the number corresponds to a specific character of the mask);        For each ‘1’ character of the mask, there is a 1 value in the corresponding bit of the number; and        For each ‘0’ character of the mask, there is a 0 value in the corresponding bit of the number.        
If one or more of the above conditions are not met, the number and the mask are incompatible. Thus, a ‘1’ or a ‘0’ character of the mask determines uniquely the value of the corresponding bit of the number. An ‘x’ character in the mask leaves the corresponding bit value of the number undetermined.
A number is constrained by requiring it to be compatible with a given mask.
Where it is not convenient to represent a floating-point machine number by a single string of bits, it is possible (although not necessary) to split such a representation into a triplet of numbers:
Sign:A string of one bit, which is 0 for a‘+' and 1 for a ‘−'. The numericalvalue is denoted by s (s = 0 or 1).Biased exponent:A string of w bits. This isinterpreted to be a binary integer withthe numerical value e, where 0 ≦ e ≦2w − 1. In a non-limiting generalizationfrom the single and double formats ofthe IEEE standard 754, Emin = 2 − 2w−1,Emax = bias = 2w−1 − 1.Significand:A string of p bits, b0b1b2 . . . bp−1. Unlikethe single and double formats of IEEEstandard 754, note that b0 is explicitlyincluded in the string. Interpretingthe string as a binary number with thebinary point placed between b0 and b1,the numerical value of the significandis S, where 0 ≦ S ≦ 2 − 21−p.
Likewise, for convenience it is possible to speak of a triplet of masks corresponding to the above triplet of numbers. For example, it is possible to prepare and manipulate a particular mask as a significand mask.
Note that the above splitting of a floating-point number (or a mask) is for convenience and is non-limiting. In particular, it is still possible to represent a complete floating-point machine number as a single sequence of bits, and it is still possible to speak of a single mask corresponding to such a complete floating-point machine number.
The value v, which corresponds to such a triplet of bit strings is given by:                1. If e=2w−1 and S≠1, then v is NaN regardless of s.        2. If e=2w−1 and S=1, then v=(−1)s×∞ (Infinity).        3. If 0<e<2w−1 and S≧1, then v=(−1)s×2e−bias×s (Normalized numbers).        4. If e=0 and S<1 then v=(−1)s×2Emin×S (Denormalized numbers and zeroes).        
Machine numbers are herein denoted in underlined italics (such as a machine number a).
Rounding
Mathematically, most numbers in the set of real numbers cannot be represented by a finite number of digits (not even the entire subset of rational numbers), and most of those rational numbers which can be represented by a finite number of digits cannot be represented by the small fixed number of digits in the various floating-point formats. It is common, therefore, that the results of a floating-point operation be adjusted, or “rounded” to fit within the confines of the floating-point representation. The result of a rounding operation is a floating-point number that approximates the precise value that should result from the computation. Rounding, when applied, always introduces an error into the computation, but this error is small enough to be ignored in the vast majority of practical applications.
In practice, the precise value is not necessarily computed, but rather an intermediate result that represents floating-point numbers using a larger number of significand bits than the permitted format of the output (also ref erred to herein as the “output result”). The rounding thus consists of a truncation of the excess digits of the intermediate result, and a possible incrementing of the least significant bit of the significand, with a possible carry of this incrementing to more significant bits of the significand.
There are several different rounding modes, all of which must be taken into account when generating test cases:                round up—round toward the closest floating-point number to the intermediate result that lies between the intermediate result and +∞.        round down—round toward the closest floating-point number to the intermediate result that lies between the intermediate result and −∞.        round to zero—round toward the closest floating-point number to the intermediate result that lies between the intermediate result and zero.        round to nearest/even—round toward the floating point number closest to the intermediate result regardless of the direction. If the intermediate result lies exactly halfway between the nearest larger floating-point number and the nearest smaller floating-point number, choose the nearest floating-point number whose least significant significand bit is zero (“even”).Coverage        
How does one know that a certain set of tests is sufficient? This question is related to the notion of coverage, that is, to the comprehensiveness of the set related to the target floating-point unit. Coverage models are usually defined, and the set of teats should fulfill all the existing requirements. A coverage model constitutes a set of related cases. Coverage modeling is discussed in “Software negligence and testing coverage” by C. Kaner, Proceedings of STAR 96: the Fifth International Conference, Software Testing, Analysis and Review, pages 299–327, June 1996; and “User defined coverage—a tool supported methodology for design verification” by R. Grinwald, E. Harel, M. Orgad, S. Ur, and A. Ziv, Proceedings of the 35th Design Automation Conference (DAC), pages 158–163, June 1998.
As an example, a common coverage model—albeit one that is far from trivial to fulfill—requires enumerating all major IEEE Floating Point types simultaneously for all operands of all FP instructions. For a given instruction with three operands, say ADD, this potentially yields in the order of a thousand (103) cases to cover, assuming 10 major FP types (±NaN's, ±Infinity, ±Zero, ±Denormal, ±Normal). This model can be further refined by adding more FP types, such as Minimum and Maximum Denormals, and so forth. Obviously, not all cases are possible (for example, the addition of two positive denormal numbers cannot reach infinity), so that the actual number of cases is in fact lower than the size of the Cartesian product. A coverage model, or the set of all coverage models, is really an attempt to partition the set of all calculation cases in such away that the probability distribution should be similar for all subsets.
A Generalized Test-Case Generator
Consider an automatic test generator whose input is the description of a coverage model, and whose output is a set of tests covering that model. A coverage model is defined by specifying a set of different constraints to be fulfilled, where each constraint corresponds to a particular task targeted by the coverage model. More precisely, a coverage model will have the form of a sequence of FP instructions, with sets of constraints on the input operand(s), the intermediate result(s), and the results of the participating instructions. Covering the model then requires providing a set of tests which display the instruction sequence, and which possesses the property that each constraint is satisfied by at least one test of the set. The general appearance of a single instruction constraint is of the following form:FPinst (Op1 in Pattern1) (Op2 in Pattern2) (IntRes in Pattern3) (Res in Pattern4)  (1)
where FPinst is a generic floating point instruction with two input operands (Op1 and Op2), one intermediate result (IntRes), and one output result (Res). The case of two input operands and a single intermediate result is used here for simplicity, but of course generalization to any number of such parameters is possible.
A Pattern is a construct representing the logical union (∪) among sets of FP numbers. The sets serve as constraints defining (in fact limiting) the allowable FP numbers for each term of expression (1). Patterns have the general following form:Pattern=Set1∪Set2∪ . . . ∪ SetN  (2)
where each Set1 is a set of FP numbers. Each task of the coverage model corresponds to a specific selection of Seti for each Pattern. Covering the task reduces then to select a data—tuple where each individual datum belongs to the corresponding selected Seti. Thus, the number of different tasks originated from a single such instruction is the product of the number of Sets for each participating Pattern. The number of tasks for a sequence is the product of the number of tasks for each individual Instruction.
There are different kinds of constraints on FP numbers:                Ranges—constraints on the upper and lower limits of a machine number or element of number triplet (for example, an exponent between 0 and 2);        Weights—constraints on the limits of the number of bits of value 1 within a machine number or element of a number triplet (for example: at least 1 bit set in the significand);        Run-length—constraints on the lengths of continuous streams of 1's and/or 0's (for example: a stream of at least 45 consecutive 1's in the significand); and        Masks—constraints on individual bits of a machine number (described herein in detail).        
It is also possible to specify a set for which the selected value should be a function of the value previously selected for another input operand. For example, a selected exponent can be at a distance of at most 2 from the exponent selected for the previous input operand. Set operations (intersection, union, complement, of same and different set types) are also possible.
For a generalized test-case generator, any architecture resource which might influence FP instruction's results is settable as an input. For example, in the non-limiting case of IEEE standard architecture, this applies to Rounding Modes and Enabled Flags.
A generalized test-case generator solves constraints that are derived from set restrictions on instruction operands. Given a restriction, the generator ideally seeks a random instance that solves the restriction, where the solutions are uniformly distributed among the set of all solutions. In practice, the complexity involved is sometimes overwhelming, especially for complex or multiple restrictions. In such cases, the generator at least ensures that each solution has a reasonable probability of being selected. As described above, constraints can be given on the input operands, the output or even on both simultaneously. It should be clear that there is a significant leap in complexity involved in solving constraints on outputs. Indeed, in contrast to the case of the input operands, the constraint on outputs includes the instruction semantics. However, even output constraints are usually solvable analytically In reasonable time complexity. Constraint restrictions start to become largely intractable when simultaneous constraints are requested on both input operands and outputs. For example, it is largely unclear how to find an instance in which the result of a MUL instruction has at least 45 bits set in its significand and the inputs are restricted by specific ranges or masks. Such a case might seem artificial, but it is often the case that cases such as this one are important to check due to specific implementation methods. Moreover, during the implementation itself, it is sometimes important to explore whether some cases are possible at all—it is desirable to know if a solution does not exist. Knowing that some cases can be neglected can be critical in optimizing the microarchitecture. In fact, in many cases, it can be shown that the constraint problem is NP-Hard. Thus, the generalized test case generator's approach for these problems should be heuristic, mixing probabilistic, search spaces and semi-analytic algorithms. Some important cases of simultaneous constraints, however, are solvable analytically, including, for example, Range constraints or Mask constraints on all operands for the FP ADD instruction.
Test Generation Via Masks
The present inventors have realized that it is possible to advantageously specify the generation of test cases using masks to constrain the floating-point numbers of the test cases, as described previously. Masks are an important way of defining sets of floating-point machine numbers by providing constraints on the bits of those numbers.
There are a number of important advantages in utilizing masks for specifying constraints in the generating of test cases:                Masks are easy to visualize, understand, and manipulate. Using masks does not require the user to develop any complicated algorithms or to write any software code, as is required for prior-art generation functions.        Masks can be easily created to describe a wide range of machine numbers having specific properties of interest to floating-point unit designers. It is common for an implementation to treat a specific bit, or set of specific bits, in a particular manner, and masks are a natural means to introduce a bias towards numbers having specific bits set to prescribed values, while the values of other bits are assigned randomly.        At the architectural level, masks allow defining all the IEEE generic types of FP numbers and symbolic objects: Normals, Denormals, infinities, zeroes, NaN's, and so forth. Thus, a coverage model handling all types of numbers and symbols is expressible through masks.        Although masks are not as general as the range, weight, or run-length constraints previously described, it is relatively straightforward to produce a finite (though possibly large) mask set which incorporates and expressed all the properties of a given range, weight, or run-length constraint.        
FIG. 1 illustrates the development of mask-constrained test cases. (Note that in this particular illustration, a floating-point number is taken as being associated with a single mask, as opposed to a triplet of masks as previously discussed.) Starting with a test concept 101, a specified floating-point operation along with some Testing Knowledge 102 is compiled into an operation, mask, and rounding specification 103, which selects a rounding mode for the given floating-point operation and a set of suitable masks 104, which includes:                Mask(s) for input operand(s); and        Mask for the output result.        
Floating-point operation, rounding mode, and mask set 104 are input to a floating-point test case generator 105. Floating-point test case generator 105 in turn outputs the floating-point operation, rounding mode, and a set of machine numbers 106, which includes:                Machine number(s) for the input operand(s); and        Machine number for the output result.        
Floating-point operation, rounding mode, and machine number set 106 constitute a solution 107. If, however, there exists no set of machine numbers 106 compatible with mask set 104 (which is possible, such as when the specified result mask is incompatible with the input operand masks given the specified floating-point operation), then there is no solution. In this case, solution 107 is a determination that no solution actually exists.
If there exists a set 106, the machine numbers thereof, along with the floating-point operation and rounding mode, would then be input to the target floating-point unit (not shown) to see if how the unit performs for the given floating-point operation on the given inputs, and if the unit produces the given output result. If the target floating-point unit properly duplicates the machine number for the output result as given in set 106, then the unit has passed this particular test. Otherwise, if the target unit does not properly duplicate the machine number for the output result as given in set 106, there is a design error in the unit which must be corrected. Likewise, if solution 107 determines that there is in fact no solution, it may be possible to test the target unit to verify that the unit in fact does not perform any computation that results in a set of machine numbers corresponding to the masks given in set 106, because doing so also indicates a design error in the unit. Thorough testing requires exercising the target floating-point unit with a large number of such test cases for a variety of conditions.
As an example (based on the concepts in IEEE standard 754), consider a hypothetical binary floating point format of eight bits, whose structure is seeeffff. Namely, there is one bit for a sign, three bits for a biased exponent and four bits for a fraction. In analogy with the IEEE formats single and double, the significand has five bits, Emin=−2, Emax=bias−3. Given three masks Ma=0100x101, Mb=001x1011, and Mc=010xx10x, the solution requires three floating point numbers a, b, and c, which are compatible with the respective masks, such that c=round (a+b). Assuming that round stands for round to nearest/even, one solution is a=01000101, b=00101011, and c=01001100.
In the scheme illustrated in FIG. 1, it is necessary to construct floating-point test-case generator 105 with the following properties in mind:                All valid solutions must have roughly the same probability of being produced by the test-case generator; and in particular,        The solution set must not arbitrarily exclude any valid solution. In other words, every valid solution must have a non-zero probability of being selected.        
Currently, however, there are no such mask-constrained floating-point test-case generators available, even for a restricted set of floating-point operations such as addition and subtraction. In order to create a floating-point test-case generator, it is necessary to have as a minimum, a floating-point test-case generator for addition and subtraction, which can solve the hollowing problem: Given masks for three machine numbers and a rounding mode, generate machine numbers a, b, and c, which are compatible with the given masks and satisfy c=round(a±b), where round corresponds to the given rounding mode.
There is thus a need for, and it would be highly advantageous to have, a mask-constrained floating-point test case generator for floating-point addition and floating-point subtraction which has the desired properties listed above. This goal is met by the present invention.